/* 
 * CMPS 258: Programming Languages
 *        Assignment 2 - Part2: "Spy" - March 24, 2008
 *        Group name: Doomsday
 *        Authors:  Ramsey Nasser (ID# 200600496) 
 *                  Hadi Abu Rislan (ID# 200600426) 
 *                  Kevin Azzam (ID# 200602033)
 * 
 * Definition of graph data structure and related functions.
 * 
 * The underground base is modeled as an undirected graph.
 */
#ifndef GRAPH_H_
#define GRAPH_H_

#include "util.h"
#include "path.h"

/*
 * A vertex in the graph.
 * 
 * Verticies maintain an adjacency list to keep track of what is connected to
 * it. 
 */
typedef struct _vertex {
	int id;					// The number identifying this vertex
} vertex;

/*
 * An edge connecting two verts
 */
typedef struct _edge {
	vertex* from;		// The vert this step is coming from
	vertex* to;			// The vert this step is going to
	
	// Assignment specific properties
	int freq;			// The number of paths this step is found in
	BOOL broken;		// Whether or not this step is broken
} edge;

typedef char GRAPH_TYPE;
#define GRAPH_DIRECTED		0
#define GRAPH_UNDIRECTED	1

/*
 * A graph of verticies.
 */
typedef struct _graph {
	int vert_count;		// The number of vertices in the graph
	int edge_count;		// The number of edges in the graph
	
	GRAPH_TYPE type;	// The type of graph (directed, undirected)
	vertex* verts;		// The list of vertices
	edge* edges;
} graph;

/*
 * Create a new empty graph
 */
graph* graph_init(GRAPH_TYPE type);

/*
 * Append a vertex to the graph.
 * 
 * Returns the id of the new vertex.
 */
int graph_add_vert(graph* g);

/*
 * Append n verts to the graph.
 * 
 * Returns a pointer to an array of ints containing the new vert ids.
 */
int* graph_add_verts(graph* g, int n);

/*
 * Connect the vertices v1 and v2.
 * 
 * In a directed graph, the direction of the edge is v1->v2.
 */
void graph_connect_verts(graph* g, int v1, int v2);

/*
 * Determine whether or not v1 is connected to v2.
 * 
 * In an undirected graph, the connection is checked both ways.
 */
int graph_are_connected(graph* g, int v1, int v2);

/*
 * Get the edge between v1 and v2.
 * 
 * Returns NULL if no such edge exists. If more than one edge connects v1 and
 * v2, then the one of them will be returned.
 */
edge* graph_get_edge(graph* g, int v1, int v2);

/*
 * Break an edge in a graph.
 */
void graph_break_edge(graph* g);

/*
 * Get all paths from v1 to v2 
 * 
 * When complete, paths will contain an array of paths from v1 to v2.
 * 
 * paths is assumed to have enough space allocated to it to hold all paths.
 * path_size is assumed to be initilized to zero.
 * 
 * The initial call to this function should set p to NULL. It is used internally. 
 */
void graph_get_all_paths(graph* g, int v1, int v2, path** paths, int* paths_size, path* p);

/*
 * Print the content of the graph.
 * 
 * Prints some redundant data for undirected graphs (0 <-> 1, 1 <-> 0), but still
 * useful for debugging.
 */
void graph_print(graph* g);

/*
 * Free resources associated with graph.
 */
void graph_free(graph* g);

#endif /*GRAPH_H_*/
